/********************************************************************
* Name: ConstExpEvalFilter.cpp: 
*
* Description:
*   Doing constant expression  evaluation. 
*   (constant folding for VInst)
*
* History:
*   Create: gxf. 2008-11-15
*
********************************************************************/

#include "crossbit/ConstExpEvalFilter.h"
#include "crossbit/UTIL.h"
#include "crossbit/GLOBAL.h"
#include <iterator>
#include <algorithm>

using namespace crossbit;
XTUint32   ConstExpEvalFilter::optCnt = 0;
XTUint32   ConstExpEvalFilter::addCnt = 0;

ConstExpEvalFilter::ConstExpEvalFilter(){
    UTIL::XTMemset(tags, 0x0, sizeof(XTInt32) * GLOBAL::MAX_VREG);
}

XTUint32 ConstExpEvalFilter::run(VBlock *vb)
{
//    vb->print(std::cout);
//    std::cout << std::endl;

    VBlock::vb_iterator Itr = vb->begin(); 
    VBlock::vb_iterator End = vb->end(); 

    table.clear();
    
// TODO: convert to inline func instead
// Const update: VREG still holds const 
//
// if Defined VREG 
//    and VREG is NOT referred
//      Delete VREG -> REF_VINST
//      Mark VREG -> CUR_VINST
//      (Re-establish mapping)
//
// else if Defined VREG
//    but VREG is referred
//      CAN NOT delete VERG -> REF_VINST 
//      (Eliminate mapping from table)
//      still Mark VREG -> CUR_VINST 
//      (Re-establish mapping)
//
// else VREG is NOT Defined before
//      Mark VREG -> CUR_VINST
//      (init mapping is enough)
//    
// if the vreg is updated, delete it from table &
// tags it not referred
//
#define MARK_CONST_UPDATE_REG(regNum)    \
    refReg = inst->getOperand(regNum).reg;  \
    tb_Itr = table.find(refReg);            \
    if ((tb_Itr = table.find(refReg)) != table.end()){  \
        if(0 == tags[refReg]){      \
            DeleteInst(tb_Itr->second, vb, Itr); \
        }   \
        else{   \
            table.erase(refReg);   \
        }   \
        table[refReg] = inst;     \
        tags[refReg] = 0;      \
    }   \
    else{   \
        table[refReg] = inst;  \
        tags[refReg] = 0;      \
    }

// None-const update: VREG does NOT hold const
//
// if Defined VREG 
//    Eliminate mapping is enough
//

#define MARK_UPDATE_REG(regNum)    \
    refReg = inst->getOperand(regNum).reg;  \
    tb_Itr = table.find(refReg);            \
    table.erase(refReg);   \
    tags[refReg] = 0;         \

// vreg still hold the const but is referred, tag this
#define MARK_REFER_REG(regNum)         \
    refReg = inst->getOperand(regNum).reg;  \
    if(table.end() != table.find(refReg)){  \
        tags[refReg] = 1;                   \
    }

    // Temporary viables
    XTRegNum    refReg;
    TB_ITR      tb_Itr;
    

    Itr = vb -> begin();
    while (Itr != vb -> end())
    {
        VInst* inst = *Itr;
        switch(inst -> getOpcode())
        {
            case OP_LI:
                // Init or update <vreg, VInst*> pairs
                MARK_CONST_UPDATE_REG(2);
                break;

            // Detect all the instructions which may affect the vregs 
            // that hold consts, include:
            // . Arithmetic:
            //    1. vreg is updated as dest. Delete item form table;
            //    2. vreg is referred as src. Tag it.
            //    3. if all operands are const (in the table), perform 
            //       constant folding;
            //
            // . MOV/LD/MAP:
            // . CONTROL/TRANSFER:
            // . SPECIAL:(EXT)
            //    1. vreg is updated as dest. Delete item form table;
            //    2. vreg is referred as src. Tag it.
            //
            /********************************************************/
            //
            // MOV/LD/MAP:
            case OP_GET:    // s1 -> v2
                MARK_UPDATE_REG(2);
                break;
            case OP_PUT:    // v1 -> s2
                MARK_REFER_REG(1);
                break;
            case OP_MOV:    // v1 -> v2
                MARK_REFER_REG(1);
                MARK_UPDATE_REG(2);
                break;
            case OP_LD:     // 
                MARK_UPDATE_REG(4);
                MARK_REFER_REG(1);
                break;
            case OP_ST:
                MARK_REFER_REG(3);
                MARK_REFER_REG(1);
                break;
            // 
            // SPECIAL:
            case OP_SEXT:
            case OP_ZEXT:
                MARK_UPDATE_REG(3);
                MARK_REFER_REG(1);
                break;
            case OP_ADDI:
                if(table.end() != table.find(inst->getOperand(2).reg)) {  
                    XTInt32 val1 = inst -> getOperand(1).imm;
                    XTInt32 val2 = (table[inst->getOperand(2).reg])->getOperand(1).imm;
                    PerformEval((XTUint32)val1, (XTUint32)val2, inst->getOperand(3).reg, Itr, vb);
                }
                else{
                    MARK_REFER_REG(1);
                    MARK_REFER_REG(2);
                    MARK_UPDATE_REG(3);
                }
                break;
                MARK_UPDATE_REG(3);
                MARK_REFER_REG(2);
                break;
            //
            // Arithmetic:
            // 2 Oprands, no eval available,
            case OP_NOT:
                MARK_UPDATE_REG(2);
                MARK_REFER_REG(1);
                break;
            // 3 Oprands, 
            case OP_ADD:
            case OP_SUB:
            case OP_AND:
            case OP_XOR:
            case OP_OR:
            case OP_SLL:
            case OP_SRL:
            case OP_SRA:
            /* TODO: Seems not supported by translator yet
            case OP_SLLV:
            case OP_SRLV:
            case OP_SRAV:
            */
                if(table.end() != table.find(inst->getOperand(1).reg) && 
                   table.end() != table.find(inst->getOperand(2).reg)){
                    XTInt32 val1 = (table[inst->getOperand(1).reg])->getOperand(1).imm;
                    XTInt32 val2 = (table[inst->getOperand(2).reg])->getOperand(1).imm;
                    PerformEval((XTUint32)val1, (XTUint32)val2, inst->getOperand(3).reg, Itr, vb);
                }
                else{
                    MARK_REFER_REG(1);
                    MARK_REFER_REG(2);
                    MARK_UPDATE_REG(3);
                }
                break;
            // 4 Oprands, 
            case OP_MUL:
            case OP_MULU:
                if(table.end() != table.find(inst->getOperand(1).reg) && 
                   table.end() != table.find(inst->getOperand(2).reg)){
                    XTInt32 val1 = (table[inst->getOperand(1).reg])->getOperand(1).imm;
                    XTInt32 val2 = (table[inst->getOperand(2).reg])->getOperand(1).imm;
                    PerformEval2((XTUint32)val1, (XTUint32)val2, inst->getOperand(3).reg, 
                                  inst->getOperand(4).reg, Itr, vb);
                }
                else{
                    MARK_REFER_REG(1);
                    MARK_REFER_REG(2);
                    MARK_UPDATE_REG(3);
                    MARK_UPDATE_REG(4);
                }
                break;
            case OP_DIV:
            case OP_DIVU:
                if(table.end() != table.find(inst->getOperand(1).reg) && 
                   table.end() != table.find(inst->getOperand(2).reg) &&
                   0 != table[inst->getOperand(2).reg]) // this will case exception
                {
                    XTInt32 val1 = (table[inst->getOperand(1).reg])->getOperand(1).imm;
                    XTInt32 val2 = (table[inst->getOperand(2).reg])->getOperand(1).imm;
                    PerformEval2((XTUint32)val1, (XTUint32)val2, inst->getOperand(3).reg, 
                                  inst->getOperand(4).reg, Itr, vb);
                }
                else{
                    MARK_REFER_REG(1);
                    MARK_REFER_REG(2);
                    MARK_UPDATE_REG(3);
                    MARK_UPDATE_REG(4);
                }
                break;
            //
            // Control-transfer:
            //
            case OP_CMP:
                MARK_REFER_REG(2);
                MARK_REFER_REG(3);
                MARK_UPDATE_REG(4);
                break;
            case OP_JMP:
                MARK_REFER_REG(1);
                break;
            case OP_BRANCH:
                MARK_REFER_REG(2);
                MARK_REFER_REG(3);
                MARK_REFER_REG(4);
                break;
            // Nothing about reg
            case OP_SYSCALL:
            case OP_CALL:
            case OP_HALT:
                break;
            default:
                // Unsupported inst in
               // assert(0);
                break;
        } // Swtich
        Itr++;
/*        std::cout << "Current Table:" << std::endl;
        for(TB_ITR i = table.begin(); i != table.end(); i++)
        {
            std::cout << (int)i->first << ":" << *(i->second) << " : " << tags[(int)i->first]<< std::endl;
        }
        std::cout << "Current code:" << std::endl;
        vb->print(std::cout);
        std::cout << std::endl;
*/    } // While

    // Delete the used LI insts after constant evaluation
    TB_ITR tb_itr = table.begin(); 
    while (tb_itr != table.end()){
        VInst* pInst = tb_itr -> second;
        XTRegNum tReg = pInst -> getOperand(2).reg;
        if(0 == tags[tReg]){
            DeleteInst(pInst, vb, Itr);
        } 
        tb_itr++;
    }

//    vb->print(std::cerr);
//    std::cerr << std::endl;
	return (XTUint32)1;
}

// Perform constant evaluation for add/subtract/shift
void ConstExpEvalFilter::PerformEval(XTUint32 val1, XTUint32 val2, 
            XTRegNum reg, VBlock::vb_iterator& Itr, VBlock* pBlock)
{
    VInst *inst = *Itr;

    XTUint32    result;
    XTUint32    tmp;
    XTInt64     tmp64;

    switch(inst -> getOpcode()){ 
        case OP_ADD: 
        case OP_ADDI: 
            result = val1 + val2;
            break;
        case OP_SUB:
            result = val1 - val2;
            break;
        case OP_AND:
            result = val1 & val2;
            break;
        case OP_XOR:
            result = val1 ^ val2;
            break;
        case OP_OR:
            result = val1 | val2;
            break;
        case OP_SLL:
            tmp = val2 % 32;
            result = ((val1 << tmp) & (0xffff << tmp)) | 
                     ((val1 >> (32 -tmp)) & (0xffff >> (32 - tmp)));
            break;
        case OP_SRL:
            tmp = val2 % 32;
            result = (val1 >> tmp) & (0xffff >> tmp) | 
                     (val1 << (32 - tmp)) & (0xffff << (32 - tmp));
            break;
        case OP_SRA:
            result = (val1 << val2);
            break;
        /* TODO: Seems not supported by translator yet
        case OP_SLLV:
            break;
        case OP_SRLV:
            break;
        case OP_SRAV:
            break;
        */
        // TODO
        default:
            assert(0); // Wrong type
            break;
    }

    // Delete the arithmetic instructions and put a LI instead
    VInst* tpInst = *Itr;
    Itr = pBlock -> erase(Itr);  
    delete tpInst;

    Itr = pBlock -> insert(Itr, LI(result, reg));
    addCnt++;

    // If the dst reg keeps a constant but is never referred
    // Then this update should delete un-referred const map (LI)
    TB_ITR tb_Itr;
    if ((tb_Itr = table.find(reg)) != table.end()){
        if(0 == tags[reg]){
            DeleteInst(tb_Itr->second, pBlock, Itr);
        } 
        else{
            table.erase(reg);
        }
    } 

    // Now the new inst hold a constant
    // Add it to the table and tag as unreferred
    table[reg] = *Itr;
    tags[reg] = 0;

}

// Perform constant evaluation for multiply/divide
void ConstExpEvalFilter::PerformEval2(XTUint32 val1, XTUint32 val2, 
        XTRegNum reg1, XTRegNum reg2, VBlock::vb_iterator& Itr, VBlock* pBlock)
{
    VInst *inst = *Itr;

    XTUint64    result;
    union{ 
        XTUint32    high; 
        XTUint32    quotient; 
    };
    union{ 
        XTUint32    low;
        XTUint32    reminder;
    };
    
    switch(inst -> getOpcode()){ 
        // TODO
        case OP_MUL:
            result  = val1 * val2;
            high    = result >> 32; // High 32bit 
            low     = (XTUint32)result;
            break;
        case OP_MULU: 
            // by lxy, gxf's cousin
            result  = ((XTInt64)val1 & 0x00000000ffffffff) *
                      ((XTInt64)val2 & 0x00000000ffffffff);
            high    = result >> 32; 
            low     = (XTUint32)result;
            break;
        case OP_DIV: 
            assert(val2 != 0);
            quotient    = val1 / val2;
            reminder    = val1 % val2;
            break;
        case OP_DIVU:
            assert(val2 != 0);
            quotient    = ((XTInt64)val1 & 0x00000000ffffffff) /
                          ((XTInt64)val2 & 0x00000000ffffffff);
            reminder    = ((XTInt64)val1 & 0x00000000ffffffff) %
                          ((XTInt64)val2 & 0x00000000ffffffff);
            break;
        default:
            assert(0); // Wrong type
            break;
    }

    // Delete the arithmetic instructions and put a LI insts instead
    VInst* tpInst = *Itr;
    Itr = pBlock -> erase(Itr);  
    delete tpInst;

    // high | quotient -> reg1 => (v1, v2, <v3>, v4)
    // low  | reminder -> reg2 => (v1, v2, v3, <v4>)
    Itr = pBlock -> insert(Itr, LI(high, reg1));
    addCnt++;

    // If the dst reg keeps a constant but is never referred
    // Then this update should delete un-referred const map (LI)
    TB_ITR tb_Itr;
    if ((tb_Itr = table.find(reg1)) != table.end()){
        if(0 == tags[reg1]){
            DeleteInst(tb_Itr->second, pBlock, Itr);
        } 
        else{
            table.erase(reg1);
        }
    } 
    Itr = pBlock -> insert(Itr, LI(low, reg2));
    addCnt++;

    // Now the new inst hold a constant
    // Add it to the table and tag as unreferred
    table[reg1] = *(Itr);
    tags[reg1] = 0;

    // If the dst reg keeps a constant but is never referred
    // Then this update should delete un-referred const map (LI)
    if ((tb_Itr = table.find(reg2)) != table.end()){
        if(0 == tags[reg2]){
            DeleteInst(tb_Itr->second, pBlock, Itr);
        } 
        else{
            table.erase(reg2);
        }
    } 

    // Now the new inst hold a constant
    // Add it to the table and tag as unreferred
    table[reg2] = *Itr;
    tags[reg2] = 0;
}

// Delete VInst from VBlock (search according to key);
void ConstExpEvalFilter::DeleteInst(VInst* curInst, VBlock* pBlock, VBlock::vb_iterator& Itr)
{
    VBlock::vb_iterator pos;
    pos = std::find(pBlock -> begin(), pBlock -> end(), curInst);

    if (pos != pBlock -> end()){
        // Get the distance of iterators
//        iterator_traits<VBlock::vb_iterator>::difference_type dist;
        int dist;
        dist = distance(pos, Itr);

        VInst * refInst = *pos;
        pos = pBlock -> erase(pos);
        delete refInst;
		
       // Itr = pos + (dist - 1);

		Itr = pos;
		if ( dist -1 > 0 ) {
			for( XTInt32 i = 0 ; i < dist - 1 ; i++ ) {
				Itr ++;
			}
		} else {
			for( XTInt32 i = 0 ; i > dist - 1 ; i-- ) {
				Itr --;
			}
		}
        optCnt++;
    }
}

